/* 
 * Contains algorithms like A* which operate on a 3D-map. The
 * algorithms are generic enough to be reusable in different modules.
 * Another advantage of this centralized approach is that the memory
 * for tile marks etc. needs to be allocated only once.
 * 
 * Rules for using the algorithms here:
 *  - You cannot use an algorithm while another one has not yet 
 *    terminated. Calling flood_search from the visit_handler of
 *    astar_search gives undefined behaviour.
 *  - Using any of the algorithms invalidates all results returned by
 *    previous invocations of any algorithm; the memory may be
 *    overwritten.
 */

#ifndef __ALGORITHM_H_
#define __ALGORITHM_H_

#include <stdbool.h>
#include "rect.h"

extern void* algorithm_memblob;
extern int algorithm_memsize;

void algorithm_init (int memsize);
void algorithm_cleanup ();

#define ASTAR_PATH_LENGTH 100
#define ASTAR_MIN_PATHS 70 // Puts constraint on accepted memory size
#define FLOOD_MIN_COORDS 400 // Puts constraint on accepted memory size

typedef struct
{
	bool found;
	bool overflow; // stack can overflow even if we do find the path
	Coord* path;
	int length; // length of path
} AstarResult;

/*
 * Finds the cheapest path from <from> to <to> within <space>.
 * The found path, together with a bitmask indicating the 
 * success/failure/error state of the algorithm is written to the
 * <result> structure.
 * 
 * <can_go> must point to a function which returns
 * non-zero if a transition between the coordinates passed to it is
 * possible.
 * 
 * <cost_step> must point to a function which returns the step
 * cost of adding the <next> coordinates to the specified <path>.
 * 
 * <cost_estimate> may point to a function which heuristically estimates
 * the cost of the remaining path from <coord> to <to>. If it is NULL,
 * a simple sum of x-, y- and z-distance is used instead.
 * 
 * If <visit_handler> is not NULL, this function gets called whenever A*
 * has visited another tile in its search. If the visit_handler then
 * returns non-zero, the algorithm aborts with the current path and
 * SEARCH_FOUND as result.
 */
void astar_search (Coord from, Coord to, Space space, AstarResult* result,
                   bool (*can_go) (Coord from, Coord to),
                   int (*cost_step) (Coord pprev, Coord prev, Coord next),
                   int (*cost_estimate) (Coord coord),
                   bool (*visit_handler) (Coord coord));

/*
 * Starting from <start>, tries to find a Coord in <space> for which
 * calling <visit_handler> returns true. The search expands in all
 * directions, taking steps of <stepx> units in x-direction and steps of
 * <stepy> units in y-direction. Locations which are closer to <start>
 * are visited before ones which are further away. The search will not
 * expand to (and visit) locations which go beyond the defined <space>
 * constraints or for which a call to <can_go> returns 0. If the search
 * should not take diagonal steps, remember to check for and disallow
 * them using <can_go>.
 * 
 * If a matching location is found (<visit_handler> returns true), the
 * search ends and returns true. If the algorithm runs out of locations
 * to expand from, it continues with the neighbouring layers (z +- 1).
 * If there are no more available layers, the search ends unsuccessfully
 * and returns false.
 */
bool flood_search (Coord start, Space space, int stepx, int stepy,
                   bool (*can_go) (Coord from, Coord to),
                   bool (*visit_handler) (Coord coord));

/*
 * Similar to flood_search, <flood_fill> examines coordinates in <space>
 * expanding from <start>. However, the algorithm also keeps track of
 * the <distance> - in coord units - that it took to reach the <coord>
 * from <start>. It does not terminate from a <visit_handler> return
 * value, but but when the search exceeds the <max_distance>. Calls to
 * <visit_handler> are made in summary at the end, for each <coord> with
 * the smallest discovered <distance>, not in the actual order of coords
 * discovered. The step size in x/y directions is always 1.
 */
void flood_fill (Coord start, Rect space, float max_distance,
                 bool (*can_go) (Coord from, Coord to),
                 void (*visit_handler) (Coord coord, float distance));

#endif /* __ALGORITHM_H_ */
